package com.sheng.leetcode.year2023.month06.day08;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/06/08
 * <p>
 * 1240. 铺瓷砖<p>
 * <p>
 * 你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。<p>
 * 房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。<p>
 * 假设正方形瓷砖的规格不限，边长都是整数。<p>
 * 请你帮设计师计算一下，最少需要用到多少块方形瓷砖？<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 2, m = 3<p>
 * 输出：3<p>
 * 解释：3 块地砖就可以铺满卧室。<p>
 * 2 块 1x1 地砖<p>
 * 1 块 2x2 地砖<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 5, m = 8<p>
 * 输出：5<p>
 * <p>
 * 示例 3：<p>
 * 输入：n = 11, m = 13<p>
 * 输出：6<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 13<p>
 * 1 <= m <= 13<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/tiling-a-rectangle-with-the-fewest-squares">1240. 铺瓷砖</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1240 {

    @Test
    public void test01() {
        int n = 2, m = 3;
//        int n = 5, m = 8;
//        int n = 11, m = 13;
        System.out.println(new Solution().tilingRectangle(n, m));
    }
}

class Solution {
    private int n;
    private int m;
    private int[] filled;
    private int ans;

    public int tilingRectangle(int n, int m) {
        this.n = n;
        this.m = m;
        ans = n * m;
        filled = new int[n];
        dfs(0, 0, 0);
        return ans;
    }

    private void dfs(int i, int j, int t) {
        if (j == m) {
            ++i;
            j = 0;
        }
        if (i == n) {
            ans = t;
            return;
        }
        if ((filled[i] >> j & 1) == 1) {
            dfs(i, j + 1, t);
        } else if (t + 1 < ans) {
            int r = 0, c = 0;
            for (int k = i; k < n; ++k) {
                if ((filled[k] >> j & 1) == 1) {
                    break;
                }
                ++r;
            }
            for (int k = j; k < m; ++k) {
                if ((filled[i] >> k & 1) == 1) {
                    break;
                }
                ++c;
            }
            int mx = Math.min(r, c);
            for (int w = 1; w <= mx; ++w) {
                for (int k = 0; k < w; ++k) {
                    filled[i + w - 1] |= 1 << (j + k);
                    filled[i + k] |= 1 << (j + w - 1);
                }
                dfs(i, j + w, t + 1);
            }
            for (int x = i; x < i + mx; ++x) {
                for (int y = j; y < j + mx; ++y) {
                    filled[x] ^= 1 << y;
                }
            }
        }
    }
}

//class Solution {
//    public int tilingRectangle(int n, int m) {
//        int[][] answers = {
//                {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13},
//                {2, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7, 6, 8},
//                {3, 3, 1, 4, 4, 2, 5, 5, 3, 6, 6, 4, 7},
//                {4, 2, 4, 1, 5, 3, 5, 2, 6, 4, 6, 3, 7},
//                {5, 4, 4, 5, 1, 5, 5, 5, 6, 2, 6, 6, 6},
//                {6, 3, 2, 3, 5, 1, 5, 4, 3, 4, 6, 2, 6},
//                {7, 5, 5, 5, 5, 5, 1, 7, 6, 6, 6, 6, 6},
//                {8, 4, 5, 2, 5, 4, 7, 1, 7, 5, 6, 3, 6},
//                {9, 6, 3, 6, 6, 3, 6, 7, 1, 6, 7, 4, 7},
//                {10, 5, 6, 4, 2, 4, 6, 5, 6, 1, 6, 5, 7},
//                {11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1, 7, 6},
//                {12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1, 7},
//                {13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1}
//        };
//        return answers[n - 1][m - 1];
//    }
//}
